5337. Разные-разные

Дано n чисел. Определите, сколько из них являются различными.

Вход. Первая строка содержит количество чисел n (1 ≤ n ≤ 10⁶). Во второй строке заданы n чисел, каждое из которых по модулю не превышает 2 ·10⁹.

Выход. Выведите количество различных чисел среди заданных.

Пример входа	Пример выхода
5 9 15 22 15 22	3

РЕШЕНИЕ

структуры данных - set

Анализ алгоритма

Решение при помощи множества set. Заносим все элементы во множество set. Каждое число будет занесено во множество только один раз. Далее выводим размер множества. Сложность O(n log₂n).

Решение с использованием сортировки. Заносим числа в массив и отсортируем его. Одинаковые числа будут расположены рядом. Проходим по массиву, подсчитываем количество различных соседних элементов. Прибавив к этому числу единицу, получаем количество различных элементов в массиве. Сложность O(n log₂n).

Реализация алгоритма

Объявим множество s.

set<int> s;

Читаем входные данные. Заносим все числа во множество.

scanf("%d",&n);

for(i = 0; i < n; i++)

{

scanf("%d",&val);

s.insert(val);

}

Выводим размер множества s – количество различных чисел среди заданных.

printf("%d\n",s.size());

Реализация алгоритма – сортировка

Читаем входные данные. Заносим входные числа в массив.

scanf("%d", &n);

v.resize(n);

for (i = 0; i < n; i++)

scanf("%d", &v[i]);

Сортируем массив.

sort(v.begin(), v.end());

Подсчитываем количество разных соседних элементов в массиве в переменной cnt. Изначально установим cnt равным 1.

cnt = 1;

for (i = 0; i < n - 1; i++)

if (v[i] != v[i + 1]) cnt++;

Выводим ответ.

printf("%d\n", cnt);

Реализация алгоритма – сортировка + unique

Читаем входные данные. Заносим входные числа в массив.

scanf("%d", &n);

v.resize(n);

for (i = 0; i < n; i++)

scanf("%d", &v[i]);

Сортируем массив.

sort(v.begin(), v.end());

Вычисляем и выводим количество различных элементов в массиве.

res = unique(v.begin(), v.end()) - v.begin();

printf("%d\n", res);

Java реализация

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

TreeSet<Integer> s = new TreeSet<Integer>();

int n = con.nextInt();

for(int i = 0; i < n; i++)

{

int val = con.nextInt();

s.add(val);

}

System.out.println(s.size());

con.close();

}

}

Java реализация – sort

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

int m[] = new int[n];

for(int i = 0; i < n; i++)

m[i] = con.nextInt();

Arrays.sort(m);

int cnt = 1;

for (int i = 0; i < n - 1; i++)

if (m[i] != m[i + 1]) cnt++;

System.out.println(cnt);

con.close();

}

}

Python реализация

Читаем входные данные.

n = int(input())

lst = list(map(int,input().split()))

Преобразуем список lst во множество, которое автоматически удаляет повторяющиеся элементы. Затем вычисляем и выводим количество элементов в этом множестве.

print(len(set(lst)))